package algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName MergeSort
 * @Date 2021/9/2 15:35
 * @Author 李明杰
 * @Description
 */

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        System.out.print(Arrays.toString(MergeSort(a)));
    }

    /**
     * 函数作用：不断的递归最终变成俩元素一个数组
     *
     * @param array
     * @return 一个排序好的数组
     */
    public static int[] MergeSort(int[] array) {

        if (array.length < 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }

    /**
     * @param left
     * @param right
     * @return 返回值合并成排序完成的数组
     */
    public static int[] merge(int[] left, int[] right) {

        int[] result = new int[left.length + right.length];

        for (int i = 0, j = 0, k = 0; k < result.length; k++) {
            if (i >= left.length)//左边空了
                result[k] = right[j++];
            else if (j >= right.length)//右边空了
                result[k] = left[i++];

            else if (left[i] > right[j])
                result[k] = right[j++];
            else
                result[k] = left[i++];
        }
        return result;
    }
}
